class Solution {
    static bool cmp(int a, int b)
    {
        return abs(a) > abs(b);
    }

public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] < 0 && k > 0)
            {
                nums[i] *= -1;
                --k;
            }
        }

        if(k > 0 && (k & 1)) nums[n - 1] *= -1;
        return reduce(nums.begin(), nums.end());
    }
};
